package com.linyaonan.leetcode.medium._382;


import org.apache.tomcat.util.buf.HexUtils;

import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
 *
 * 实现 Solution 类：
 *
 * Solution(ListNode head) 使用整数数组初始化对象。
 * int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/linked-list-random-node
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    int allCount = 0;
    ListNode org;
    /**
     * 思路1：首先得到链表的长度，然后创建一个随机器返回随机值
     * @param head
     */
    public Solution(ListNode head) {
        org = head;
        while (head !=null) {
            allCount++;
            head = head.next;
        }
    }
    
    public int getRandom() {
        int i = ThreadLocalRandom.current().nextInt(allCount);
        ListNode r = org;
        while (i-- != 0) {
            r = r.next;
        }
        return r.val;
    }

}